In image processing, edge detection and line segment (or spline) extraction are often necessary steps for operations including object detection and recognition. For example, many current face detection methods include edge detection and spline extraction as a part of their operation. Edge detection is used to process a digital image into an edge image, where the edge image comprises only edge pixels. Line segment extraction is then used to process the edge image into a plurality of line segments, or splines. Each spline is a straight line segment without any corners. Splines may contact each other at their end points, but not at any other location within the spline.
Since splines are straight lines, they may be easily described mathematically by a line equation, or simply by defining their end points. This allows further image processing operations to operate efficiently for such purposes as object detection and recognition. Speed and accuracy are critical to any method for spline extraction from edge images. Faster spline extraction methods are useful in particular when analyzing video data where new images are captured at the frame rate of the video source. Accuracy may be critical in many different image processing methods since incorrect splines may render latter image processing operations invalid.
Overview
In an embodiment, a method for extracting line segments from an edge image comprises receiving a digital image comprising a plurality of edge pixels, and processing the plurality of edge pixels using a breadth first search to determine a plurality of breadth first search pixels in a breadth first search order for a connected component. The connected component comprises a plurality of components. The method continues by processing the plurality of breadth first search pixels in an order related to the breadth first search order to determine a plurality of component pixels for at least one component of the plurality of components. Each of the plurality of components comprises a line segment. The method concludes by processing the plurality of component pixels to determine a plurality of line segment pixels for the line segment.
In some embodiments, processing the plurality of edge pixels using a breadth first search to determine a plurality of breadth first search pixels in a breadth first search order for a connected component comprises scanning the digital image until an edge pixel not contained in any previously created connected component is detected, and creating a connected component containing the edge pixel. The digital image is then processed using a breadth first search to produce a list of breadth first search pixels connected to the edge pixel and breadth first search distances to the edge pixel, and the list of breadth first search pixels and breadth first search distances is added to the connected component.
In an embodiment, processing the plurality of breadth first search pixels in an order related to the breadth first search order to determine a plurality of component pixels for at least one component of the plurality of components comprises selecting a connected component, and processing the list of breadth first search pixels from the selected connected component in reverse order, starting from the final breadth first search pixel, to produce the list of components.
Processing the list of breadth first search pixels in reverse order, starting from the final breadth first search pixel, to produce the list of components may comprise selecting a pixel from the list of breadth first search pixels, and determining if the pixel belongs to the end of one or more previously created component. If the pixel does not belong to an end of any previously created component, a new leaf component containing the pixel is created. If the pixel belongs to the end of one previously created component, the pixel is added to the list of component pixels for the one previously created component. If the pixel belongs to more than one previously created component the lengths of each of the more than one previously created component is determined.
If more than one of the previously created components are either non-leaf components or are not shorter than a component threshold, a new non-leaf component containing the pixel is created. If only one of the previously created components is either a non-leaf component or is longer than the component threshold, all of the leaf components that have lengths less than the component threshold are deleted. If none of the previously created components are either non-leaf components or are longer than the component threshold, all of the leaf components that have lengths less than the component threshold are deleted. If all of the previously created components have lengths less than the component threshold, all of the previously created components except for the longest previously created component are deleted and the pixel is added to the longest previously created component.
Processing the plurality of component pixels to determine a plurality of line segment pixels for the line segment may comprise selecting a component from the list of components, selecting a starting pixel from the list of component pixels for the component, and creating a current line segment containing the starting pixel. The list of component pixels for the component is processed in order by selecting a current pixel from the list of component pixels for the component, adding the current pixel to the current line segment, processing the current line segment to produce a current spline representation, calculating a distance between at least some of the pixels in the current line segment and the current spline representation, comparing the distance to a spline threshold, and closing the current line segment and creating a new line segment containing the current pixel if the distance is greater than the spline threshold.
In an embodiment, the component threshold and the spline threshold may be set by a user.
In another embodiment, the image is a processed digital image from a transit system, and at least some of the edges define outlines of human heads.
In a further embodiment an image processing system for extracting line segments from a digital image comprises an interface configured to receive images, and a processor electrically coupled with the interface. The processor is configured to receiving a digital image comprising a plurality of edge pixels, and to process the plurality of edge pixels using a breadth first search to determine a plurality of breadth first search pixels in a breadth first search order for a connected component. The connected component comprises a plurality of components. The processor continues by processing the plurality of breadth first search pixels in an order related to the breadth first search order to determine a plurality of component pixels for at least one component of the plurality of components. Each of the plurality of components comprises a line segment. Finally, the processor processes the plurality of component pixels to determine a plurality of line segment pixels for the line segment.
In a further embodiment, a computer-readable medium having instructions stored thereon for operating a computer system to extract line segments from a digital image is described. The instructions, when executed by the computer system, direct the computer system to receive a digital image comprising a plurality of edge pixels, and process the plurality of edge pixels using a breadth first search to determine a plurality of breadth first search pixels in a breadth first search order for a connected component. The connected component comprises a plurality of components. The instructions, when executed by the computer system, also direct the computer system to process the plurality of breadth first search pixels in an order related to the breadth first search order to determine a plurality of component pixels for at least one component of the plurality of components. Each of the plurality of components comprises a line segment. The instructions, when executed by the computer system, also direct the computer system to process the plurality of component pixels to determine a plurality of line segment pixels for the line segment.